1. Field of the Invention
The present invention relates generally to systems and processes for scheduling complex jobs, and specifically to a scheduling system and process using limited discrepancy search techniques.
2. Description of Related Art
A class of problems known as "Constraint-Satisfaction Problems" (CSPs) arises often in diverse areas such as human resource allocation, artificial vision, event planning, map coloring, and the like. These problems are characterized in having a set of elements and a set of possible attributes, and in calling for a particular assignment of attributes to elements. An example of a CSP might be the problem of how to staff the night shift of a factory with at least one person who is intelligent and at least one person who is strong. Another, slightly more general, example is scheduling the jobs required, using finite available resources, to construct a prototype of a new product by a target date.
Processes using artificial intelligence (AI) techniques have been applied to CSPs not only to permit managers to allocate human and other resources in a feasible manner, but in a wide range of other diverse situations, for instance to help planners determine feasible schedules for meetings, to assist scientists in interpreting images from artificial vision devices, and even to allow cartographers to select colors for countries or other municipal areas when designing maps.
Two primary approaches have been taken in attempting to deal with such situations using artificial intelligence. The first is known as "systematic" because under this approach, every possible set of element-attribute pairings is eventually considered, unless a set of pairings that meets all of the constraints is found at some point in the process. These processes often rely on maintaining a database of possible reasons why certain assignments, or groups of assignments, will not satisfy the constraints of the CSP. The sets of reasons indicating assignments that do not work are commonly referred to as sets of "nogoods". When a process of this class fails to provide a set of workable assignments, one can be sure that no workable set of assignments exists. Numerous such systematic processes are known, for instance as described in M. L. Ginsberg, Dynamic Backtracking, JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH 1:25-46, 1993.
The second class is known as "nonsystematic" and is typically faster to find a solution. However, because processes of this class do not keep track of whether they have considered all possible sets of element-attribute pairings, where such processes do not yield a solution, one cannot know whether a workable set of assignments exists but has not been found, or whether no workable set of assignments exists. A well-known example of such a nonsystematic technique is the GSAT technique, now known under an improved version as WSAT and described in B. Selman, et al., Local Search Strategies for Satisfiability Testing, PROCEEDINGS 1993 DIMACS WORKSHOP ON MAXIMUM CLIQUE, GRAPH COLORING, AND SATISFIABILITY, 1993.
Several other known strategies within these two broad classes of processes have been employed to solve CSPs.
One known process is to simply apply a heuristic, or "rule of thumb," and to see whether the heuristic results in an acceptable solution. One such heuristic might be: If machine A is available, use it; otherwise if machine B is available use it; otherwise if machine C is available use it; otherwise wait for machine A to finish and then use it. In some instances, such a technique works very well and provides a simple solution. When the heuristic fails, however, alternate techniques must be used.
One possible alternate scheme, known as iterative sampling, or isamp, involves following random paths, or probes, from a starting point until eventually a path leading to an acceptable solution is discovered. At each node on a path, one of the successor nodes is selected at random and followed; next, one of the successors to that node is selected, and so on, until either a "goal node", i.e., acceptable solution, or a dead end is reached. If a path terminates at a dead end, a new probe is begun from the original starting point.
This process samples with replacement, resulting in a uniform chance of finding a goal node on any particular probe. Accordingly, the probability of achieving a goal node progresses uniformly to 1 as the number of probes grows without limit.
Iterative sampling works well in applications exhibiting high solution densities, but not otherwise.
Another scheme, known as "backtracking," uses the heuristic approach as far as possible. When the heuristic is found to fail, the last decision before the failure is changed, unless all possible changes at that point have already been tried. If they have, the decision prior to that is changed, and so on. This process works well where heuristics early in the process are more reliable than those later in the process, because it does not revisit the earliest decisions until all of the subsequent paths have been found to fail. Unfortunately, in most real-world problems, heuristics generally become more reliable as a solution is approached and the problem is reduced in size.
Known processes for handling CSPs are all lacking in one way or another, particularly when applied to job scheduling problems. Known systematic approaches are computationally quite slow. Known nonsystematic approaches are unable to report with certainty the absence of a workable set of assignments. Furthermore, techniques such as GSAT perform very poorly in situations where there is no way to tell when one is "close" to a workable set of assignments. An example of a situation to which GSAT is not well suited is the CSP of generating a crossword puzzle by filling words from a fixed dictionary into a given frame, i.e., assigning letter attributes to square elements. GSAT falters here because a conflict at a single square may require reassignment of a large portion of the other words in the puzzle.
None of the known teachings provides an adequately robust process that does not suffer from these failings.
It would be helpful if a process and corresponding system could effectively combine systematic and non-systematic approaches to efficiently reach solutions to CSPs such as resource allocation and scheduling problems.